Soit $E=\{n\in \mathbb{N}^*\textrm{, } n=ax+by \textrm{ avec } (x,y)\in\mathbb{Z}^2 .\}$

1. Montrer que $E$ n'est pas vide.
   $E$ admet donc un plus petit élément que l'on note $n_0$.
2. Montrer que $D$ divise $n_0$.
   Ainsi $D\leq n_0$.
3. La division euclidienne de $a$ par $n_0$ montre qu'ils existent $0\leq r <n_0$ et $q$ entier relatif tel que $a=n_0q+r$.
   Montrer que $r=a(1-qu)+b(-qv)$.
4. En déduire que $r=0$ et donc que $n_0$ divise $a$.
5. On montre de même que $n_0$ divise $b$. Montrer alors que $n_0\leq D$.
6. En déduire que $D=n_0$ et conclure.

Recherche d'un couple $(u,v)$ tel que : $au+bv=PGCD(a,b)$ On considère les entiers $a=266$ et $b=244$.

1. Calculer le $PGCD(a,b)$ en utilisant l'algorithme d'Euclide.
2. A l'aide des égalités écrites précédemment déterminer deux entiers relatifs $u$ et $v$ tels que : $$au+bv=PGCD(a,b)$$

Démonstration

1. Montrer le sens direct.
2. Montrer le sens réciproque.

1. Soit un entier naturel $k$. Montrer que le $PGCD(1+3k,1+4k)=1$
2. En déduire que si un entier naturel $n$ est congru à 1 modulo 7, alors : $PGCD(3n+4,4n+3)=7$

Démonstration

Indication : Utiliser le théorème de Bézout pour démontrer le théorème.

1. Calculer $d=PGCD(495,150)$.
2. Déterminer des entiers $u$ et $v$ tels que : $$495u+150v=d.$$

On considère des entiers naturels non nuls.

1. Démontrer que deux entiers consécutifs sont toujours premiers entre eux.
2. Deux entiers impairs consécutifs sont-ils toujours premiers entre eux? Justifier.
3. Deux entiers pairs peuvent-ils être premiers entre eux? Justifier.

1. Démontrer que les entiers $a=39$ et $b=50$ sont premiers entre eux.
2. Justifier l'existence de deux entiers $u$ et $v$ tels que $39u+50v=1$. Déterminer un couple $(u,v)$.

Soit $p$ un nombre premier $a$ et $b$ deux entiers non nuls.
Démontrer que $p$ divise le produit $ab$ si, et seulement si, $p$ divise $a$ ou $p$ divise $b$.

Equation diophantienne

1. Déterminer $PGCD(2688,3024)$.
2. On cherche à déterminer tous les couples d'entiers relatifs $(x;y)$ solutions de : $$(E):2688x+3024y=-3360.$$
   1. Démontrer que l'équation $(E)$ est équivalente à l'équation : $8x+9y=-10$.
   2. Vérifier que le couple $(1;-2)$ est solution de $(E)$.
3. 1. Démontrer que si le couple $(x;y)$ est solution de $(E)$, alors $8(x-1)=9(-y-2)$.
   2. En déduire que si le couple $(x;y)$ est solution de $(E)$, alors il existe un entier $k$ tel que : $$x=1+9k \textrm{ et }y=-2-8k.$$
4. Quel est l'ensemble des couples solutions de l'équation $(E)$?

Vrai ou faux?

Préciser si les affirmations suivantes sont vraies ou fausses. Justifier la réponse.

1. $a$ désigne un entier relatif non nul.
   1. Si 5 divise $2a$, alors $a$ divise 5.
   2. Si 6 divise $9a$, alors 2 divise $a$.
   3. Si $PGCD(a,5)=1$ et $a$ divise 500, alors $a$ divise 4.
2. $a$, $b$ et $c$ désignent des entiers relatifs non nuls tels que $a$ divise $bc$.
   1. Si $a$ divise $c$, alors $a$ est premier avec $b$.
   2. Si $b$ est premier, alors $a$ divise $c$.